package com.ljy.my_study.leetcode.二叉树的锯齿形层序遍历;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.*;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/11/16 16:48
 */
public class TestMain {

//    给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
//
//    例如：
//    给定二叉树 [3,9,20,null,null,15,7],
//
//            3
//            / \
//            9  20
//            /  \
//            15   7
//    返回锯齿形层序遍历如下：
//
//            [
//            [3],
//            [20,9],
//            [15,7]
//            ]
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        TreeNode root=TreeNodeUtil.deserialize("3,9,20,null,null,15,7");
        System.out.println(new TestMain().zigzagLevelOrder(root));
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return result;
        }
        queue.add(root);
        int size=1;
        boolean fromLeft=true;
        while(!queue.isEmpty()){
            int newSize=0;
            Integer[] array=new Integer[size];
            int i;
            int add;
            if(fromLeft){
                i=0;
                add=1;
            }else{
                i=size-1;
                add=-1;
            }
            for(;0<=i&&i<size;i+=add){
                TreeNode node=queue.poll();
                array[i]=node.val;
                if(node.left!=null){
                    queue.add(node.left);
                    newSize++;
                }
                if(node.right!=null){
                    queue.add(node.right);
                    newSize++;
                }
            }
            result.add(Arrays.asList(array));
            size=newSize;
            fromLeft=!fromLeft;
        }
        return result;
    }
}
